package exercises.leetcode;

/**
 * <a href="https://leetcode-cn.com/problems/divide-two-integers/">
 * 29. 两数相除</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
 * <p>
 * 返回被除数 dividend 除以除数 divisor 得到的商。
 * <p>
 * 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
 *
 * @author or2
 * @date 2021年10月12日 时间: 7:56
 */
public class No29 {
    public int divide(int dividend, int divisor) {
        if (dividend == 0x8000_0000) {
            if (divisor == 1) return 0x8000_0000;
            else if (divisor == -1) return 0x7fff_ffff;
        } else if (dividend == 0) return 0;
        if (divisor == 0x8000_0000) return dividend == 0x8000_0000 ? 1 : 0;

        int isRev = 0;
        if (dividend > 0) {
            dividend = -dividend;
            isRev ^= 1;
        }
        if (divisor > 0) {
            divisor = -divisor;
            isRev ^= 1;
        }

        int max = divisor;
        while (max >= dividend - max)
            max <<= 1;

        int ans = 0;
        while (max <= divisor) {
            ans <<= 1;
            if (max >= dividend) {
                ans += 1;
                dividend -= max;
            }
            if (max == -1) max++;
            max >>= 1;
        }

        return isRev == 1 ? -ans : ans;
    }
}
